package com.note.feng.leetcode.algorithms.easy.five;

public class FiveHundredFiftySeven {
    /**
     * 557 反转字符串中的单词 III
     * 给定一个字符串 s ，你需要反转字符串中每个单词的字符顺序，同时仍保留空格和单词的初始顺序。
     *
     * 示例 1：
     *
     * 输入：s = "Let's take LeetCode contest"
     * 输出："s'teL ekat edoCteeL tsetnoc"
     * 示例 2:
     *
     * 输入： s = "God Ding"
     * 输出："doG gniD"
     *  
     * 提示：
     *
     * 1 <= s.length <= 5 * 104
     * s 包含可打印的 ASCII 字符。
     * s 不包含任何开头或结尾空格。
     * s 里 至少 有一个词。
     * s 中的所有单词都用一个空格隔开。
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode.cn/problems/reverse-words-in-a-string-iii
     */
    /**
     * 解法：
     * 遇到空格，就反转前面的最后一个单词
     * 注意：遍历完成后，需要反转最后一个单词
     * @param s
     * @return
     */
    public String reverseWords(String s) {
        int left= 0;
        char [] chars = s.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            if(chars[i] == ' '){
                reverse(chars, left, i - 1);
                left = i + 1;
            }
        }
        reverse(chars, left, chars.length - 1);
        return new String(chars);
    }

    private void reverse(char [] arr, int left, int right){
        while (left < right){
            char tmp = arr[left];
            arr[left] = arr[right];
            arr[right] = tmp;
            left ++;
            right --;
        }
    }
}
